# coding=utf-8

import Queue as Que;

# class Friend:
#     def __init__(self , id , common_fri):
#         self.id = id
#         self.common_fri = common_fri


que = Que.Queue()
edges = []
degrees = []
level = []
common_fri = []
# 表示有n个点
def init(n):
    for i in range(1 , n+2 , 1):
        edges.append([])
        degrees.append(0)
        level.append(-1)
        common_fri.append(0)

# 添加一条x->y的边
def add_edge(x , y):
    edges[x].append(y)
    degrees[x] += 1

# 找到st的二度好友并根据他们拥有的共同好友的数量从大到小输出出来
def dijkstra(st , n):
    que.put(st)
    level[st] = 0
    while not que.empty():
        u = que.get()

        if level[u]>2:
            break
        for v in edges[u]:
            if level[v]==-1:
                level[v] = level[u]+1
                que.put(v)
            if level[u]==1 and level[v]>1: #出现了一个公共好友且它不是直接好友
                common_fri[v] += 1

    list = []
    for i in range(1 , n+1 , 1):
        if common_fri[i]>0:
            list.append((i,common_fri[i]))
    list.sort(key=lambda x:(x[1],x[0]))
    list.reverse()
    return list

#启动函数,传入点的个数n和边paths
def solve(st , n , paths):
    init(n)
    for path in paths:
        add_edge(path[0] , path[1])
    list = dijkstra(st,n)
    print list

paths = [(1,2) , (1,3) , (2,3) , (2,4) , (2,6) , (4,7) , (3,5) , (3,4),(3,7),(3,8),(4,6),(4,7)]
solve(1,8,paths)